"""
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
"""


class Solution:
    # def addBinary(self, a: str, b: str) -> str:
    def addBinary(self, a, b):
        extern = []
        if len(a) > len(b):
            extern = list(a[0 : len(a) - len(b)])
            a = a[len(a) - len(b) :]
        else:
            extern = list(b[0 : len(b) - len(a)])
            b = b[len(b) - len(a) :]
        carryNum = 0
        c = [0] * len(a)
        for i in range(len(a) - 1, -1, -1):
            result = int(a[i]) + int(b[i]) + carryNum
            if result <= 1:
                c[i] = str(result)
                carryNum = 0
            else:
                if result == 2:
                    c[i] = "0"
                else:  # 3
                    c[i] = "1"
                carryNum = 1

        for i in range(len(extern) - 1, -1, -1):
            result = int(extern[i]) + carryNum
            if result <= 1:
                extern[i] = str(result)
                carryNum = 0
            else:
                extern[i] = "0"
                carryNum = 1
        extern.extend(c)
        if carryNum == 1:
            return "1" + "".join(extern)
        else:
            return "".join(extern)


# print(Solution().addBinary("11","1")) # "100"
# print(Solution().addBinary("1010","1011")) # "10101"
